package top.trusim.list;

/**
 * 两数之和
 */
public class TwoNumSum {

    /**
     * 递归实现
     *
     * @param listOne
     * @param listTwo
     * @return
     */
    public ListNode twoNumSum(ListNode listOne, ListNode listTwo) {
        ListNode res = null;
        if (listOne == null && listTwo == null) {
            return null;
        }
        if (listOne == null) {
            return listTwo;
        }
        if (listTwo == null) {
            return listOne;
        }
        if (listOne.val + listTwo.val < 10) {
            res = new ListNode(listOne.val + listTwo.val);
            res.next = twoNumSum(listOne.next, listTwo.next);

        } else {
            res = new ListNode(listOne.val + listTwo.val - 10);
            res.next = twoNumSum(listOne.next, twoNumSum(listTwo.next, new ListNode(1)));
        }

        return res;
    }

    /**
     * 迭代实现
     *
     * @param listOne
     * @param listTwo
     * @return
     */
    public ListNode twoNumSumWithOutRecursive(ListNode listOne, ListNode listTwo) {

        if(listOne == null || listTwo == null) {
            return null;
        }
        boolean one = false;
        ListNode head = null, tail = null;
        while (listOne != null || listTwo != null) {
            int val = 0;
            if(listOne != null) {
                val += listOne.val;
                listOne = listOne.next;
            }
            if(listTwo != null) {
                val += listTwo.val;
                listTwo = listTwo.next;
            }
            if(one) {
                val += 1;
            }
            if(val >= 10) {
                val -= 10;
                one = true;
            }else {
                one = false;
            }
            if(head == null) {
                head = tail = new ListNode(val);
            }else {
                tail.next = new ListNode(val);
                tail = tail.next;
            }
        }
        if(one) {
            tail.next = new ListNode(1);
        }
        return head;

    }

    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int[] arr) {
            ListNode cur = this;
            this.val = arr[0];
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode head = this;
            while (head != null) {
                sb.append(head.val);
                if (head.next != null) {
                    sb.append("->");
                }
                head = head.next;
            }
            return sb.toString();
        }
    }


}
